package problem452;

import java.util.Arrays;

//452.用最少数量的箭引爆气球
//https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/

class Solution {
    public int findMinArrowShots(int[][] points) {
        int n = points.length;
        int ret = 0;
        Arrays.sort(points,(a, b)->{
            if(a[0] > b[0]) return 1;
            else if(a[0] < b[0]) return -1;
            else return 0;
        });

        int left = points[0][0], right = points[0][1];
        for(int i = 1; i<n; i++) {
            if(points[i][0] > right) {
                left = points[i][0];
                right = points[i][1];
                ret++;
            }else {
                left = Math.max(left, points[i][0]);
                right = Math.min(right,points[i][1]);
            }
        }
        return ret+1;
    }
}